#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>

typedef struct node
{
	int data;
	struct node* next;
} Node;

Node* NewNode(int data) {
	Node* node = malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	return node;
}

Node* BuildOneTwoThree()
{
	Node* head = NULL;
	Node* second = NULL;
	Node* third = NULL;

	head = malloc(sizeof(Node));
	second = malloc(sizeof(Node));
	third = malloc(sizeof(Node));

	head->data = 1;
	head->next = second;

	second->data = 2;
	second->next = third;

	third->data = 3;
	third->next = NULL;

	return head;
};

void printList(Node* head)
{
	Node* ptr = head;
	while (ptr)
	{
		printf("%d -> ", ptr->data);
		ptr = ptr->next;
	}
	printf("null\n");
}

int Length(Node* head) {
	Node* current = head;
	int count = 0;

	while (current != NULL) {
		count++;
		current = current->next;
	}

	return count;
}

/*
  the list is passed in as a "reference" pointer to the head pointer
  -- this allows us to modify the caller's memory.
  The headRef parameter to Push() is not the real head of the list.
  It is a pointer to the real head of the list back in the caller’s memory space.
*/
void Push(Node** headRef, int newData) {
	Node* newNode = malloc(sizeof(Node));
	newNode->data = newData;
	newNode->next = *headRef; // The '*' to dereferences back to the real head
	*headRef = newNode;
}

/*
  Given a list and an int, return the number of times
  that int occurs in the list.
*/
int Count(Node* head, int searchFor) {
	int count = 0;
	for (Node* current = head; current != NULL; current = current->next) {
		if (current->data == searchFor) count++;
	}
	return count;
}

void CountTest() {
	Node* myList = BuildOneTwoThree();
	Push(&myList, 2);
	int count = Count(myList, 2);
	printf("%d\n", count);
}

/*
  Given a list and an index, return the data in the nth node of the list.
  The nodes are numbered from 0.
  Assert fails if the index is invalid (outside 0...length-1).
*/
int GetNth(Node* head, int index) {
	int len = Length(head);
	Node* currentNode = head;
	assert(index <= len - 1);
	assert(index >= 0);
	for (int i = 0; i < index; ++i)
	{
		currentNode = currentNode->next;
	}
	return currentNode->data;
}

void GetNthTest() {
	Node* myList = BuildOneTwoThree();
	int lastNode = GetNth(myList, 2);
	printf("%d\n", lastNode);
}

/*
  DeleteList() takes a list, deallocates all of its memory and sets itshead pointer to NULL (the empty list).
*/
void DeleteList(Node** headRef) {
	Node* nextNode = NULL;
	for (Node* current = *headRef; current != NULL;)
	{
		nextNode = current->next;
		free(current);
		current = nextNode;
	}
	*headRef = NULL;
}

void DeleteListTest() {
	Node* myList = BuildOneTwoThree();
	DeleteList(&myList);
}

/*
   The opposite of Push().
   Takes a non-empty list and removes the front node,
   and returns the data which was in that node.
*/
int Pop(Node** headRef) {
	Node* head = *headRef;
	int headData = head->data;
	*headRef = head->next;
	free(head);
	return headData;
}

void Poptest() {
	Node* head = BuildOneTwoThree();
	int a = Pop(&head);
	int b = Pop(&head);
	int c = Pop(&head);
	int len = Length(head);
	printf("%d\n", a);
	printf("%d\n", b);
	printf("%d\n", c);
	printf("%d\n", len);
}

/*
  A more general version of Push().
  Given a list, an index 'n' in the range 0..length,
  and a data element, add a new node to the list
  so that it has the given index.
*/
void InsertNth(Node** headRef, int index, int data) {
	int len = Length(*headRef);
	assert(index <= len);
	assert(index >= 0);
	Node* prev = *headRef;
	if (index == 0) {
		Push(headRef, data);
	} else {
		for (int i = 1; i < index; ++i) {
			prev = prev->next;
		}
		Node* newNode = malloc(sizeof(Node));
		newNode->data = data;
		newNode->next = prev->next;
		prev->next = newNode;
	}
}

void InsertNthTest() {
	Node* head = NULL;
	InsertNth(&head, 0, 13);
	InsertNth(&head, 1, 42);
	InsertNth(&head, 1, 5);
	DeleteList(&head);
}

/* Function to insert given node into the correct sorted position in given
list sorted in increasing order using dummy node strategy for head end */
void SortedInsert(Node** headRef, Node* newNode) {
	Node* current = *headRef;
	while (current->next != NULL && (current->next->data <= newNode->data))
	{
		current = current->next;
	}
	newNode->next = current->next;
	current->next = newNode;
}

// Given a list, change it to be sorted order. (using SortedInsert())
void InsertSort(Node** headRef) {
	Node* newNode = malloc(sizeof(Node));
	newNode->next = NULL;
	for (Node* current = *headRef; current != NULL;)
	{
		Node* temp = current->next; //这个临时变量用来保存传进来的链表，防止执行完SortedInsert()后跟丢
		SortedInsert(&newNode, current);
		current = temp;
	}
	*headRef = newNode->next;

}

// Append 'b' onto the end of 'a', and then set 'b' to NULL.
void Append(Node** aRef, Node** bRef) {
	Node* aEnd = *aRef;
	while (aEnd->next != NULL) {
		aEnd = aEnd->next;
	}
	aEnd->next = *bRef;
	*bRef = NULL;
}

/*
  Split the nodes of the given list into front and back halves,
  and return the two lists using the reference parameters.
  If the length is odd, the extra node should go in the front list.
*/
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
	int len = Length(source);
	assert(len > 1);
	Push(&source, 0); //增加一个虚拟头节点
	Node *slow, *fast;
	if (len % 2 == 0) {
		for (slow = source, fast = source; fast->next != NULL; slow = slow->next, fast = fast->next->next) {}
	} else {
		for (slow = source, fast = source; fast->next != NULL; slow = slow->next) {
			if (fast->next->next == NULL) {
				fast = fast->next;
			} else {
				fast = fast->next->next;
			}
		}
	}

	*backRef = slow->next;
	slow->next = NULL;
	Pop(&source); //删除虚拟头节点
	*frontRef = source;
}

void FrontBackSplitTest() {
	Node *front = NULL, *rear = NULL;
	Node *myList1 = BuildOneTwoThree();
	Push(&myList1, 4);
	Push(&myList1, 5);
	Node *myList2 = BuildOneTwoThree();
	Node *myList3 = BuildOneTwoThree();
	Pop(&myList3);
	printf("Complete Linked list: ");
	printList(myList1);

	FrontBackSplit(myList1, &front, &rear);

	printf("\nFront: ");
	printList(front);

	printf("\nRear: ");
	printList(rear);
}

// Remove duplicates from a sorted list.
void RemoveDuplicates(Node* head) {
	if (head == NULL) return;
	for (Node *slow = head, *fast = head->next; fast != NULL;) {
		if (slow->data == fast->data) {
			fast = fast->next;
			free(slow->next);
			slow->next = fast;
		} else {
			slow = slow->next;
			fast = fast->next;
		}
	}
}

/*
  Take the node from the front of the source,
  and move it to the front of the dest.
  It is an error to call this with the source list empty.

  Before calling MoveNode():
    source == {1, 2, 3}
    dest == {1, 2, 3}

  Affter calling MoveNode():
    source == {2, 3}
    dest == {1, 1, 2, 3}
*/
void MoveNode(Node** destRef, Node** sourceRef) {
	Node *temp = (*sourceRef)->next;
	(*sourceRef)->next = *destRef;
	*destRef = *sourceRef;
	*sourceRef = temp;
}

void MoveNodeTest() {
	Node* a = BuildOneTwoThree();
	Node* b = BuildOneTwoThree();
	MoveNode(&a, &b);
	printList(a);
	printList(b);
}

/* Given the source list, split its nodes into two shorter lists.
If we number the elements 0, 1, 2, ... then all the even elements
should go in the first list, and all the odd elements in the second.
The elements in the new lists may be in any order. */
void AlternatingSplit(Node* source, Node** aRef, Node** bRef) {
	for (Node *current = source; current != NULL;)
	{
		MoveNode(aRef, &current);
		if (current != NULL) {
			MoveNode(bRef, &current);
		}
	}
}

/* Merge the nodes of the two lists into a single list taking
a node alternately from each list, and return the new list. */
Node* ShuffleMerge(Node* a, Node* b) {
	Node *head = a;
	for (Node *a_next = a->next; a != NULL;)
	{
		MoveNode(&a_next, &b);
		printList(b);
		a->next = a_next;
		a = a->next->next;
		if (a != NULL)
			a_next = a->next;
	}
	return head;
}

void ShuffleMergeTest() {
	Node *p = NULL, *q = NULL;
	Push(&p, 3);
	Push(&p, 2);
	Push(&p, 1);
	printf("First Linked List:\n");
	printList(p);

	Push(&q, 8);
	Push(&q, 7);
	Push(&q, 6);
	Push(&q, 5);
	Push(&q, 4);
	printf("Second Linked List:\n");
	printList(q);

	Node *result = ShuffleMerge(p, q);

	printf("Modified First Linked List:\n");
	printList(result);

	getchar();
}

/* Takes two lists sorted in increasing order, and splices their
nodes together to make one big sorted list which is returned. */
Node* SortedMerge(Node* a, Node* b) {
	Node* dummy = NewNode(0);
	Node* tail = dummy;
	while (1) {
		if (a == NULL) {
			tail->next = b;
			break;
		} else if (b == NULL) {
			tail->next = a;
			break;
		}
		if (a->data <= b->data) {
			MoveNode(&tail->next, &a);
		} else {
			MoveNode(&tail->next, &b);
		}
		tail = tail->next;
	}
	return dummy->next;
}

void SortedMergeTest() {
	Node* head1 = NewNode(1);
	head1->next = NewNode(3);
	head1->next->next = NewNode(5);

	// 1->3->5 LinkedList created

	Node* head2 = NewNode(2);
	head2->next = NewNode(4);
	head2->next->next = NewNode(4);

	// 0->2->4 LinkedList created

	Node* mergedhead = SortedMerge(head1, head2);

	printList(mergedhead);
	getchar();
}

// MergeSort() is often preferred for sorting a linked list
void MergeSort(Node** headRef) {
	Node *head = *headRef;
	Node *a = NULL, *b = NULL;
	if (head == NULL || head->next == NULL) {
		return;
	} else {
		FrontBackSplit(head, &a, &b);
		MergeSort(&a);
		MergeSort(&b);
		*headRef = SortedMerge(a, b);
	}
}

void MergeSortTest() {
	/* Start with the empty list */
	// Node* res = NULL;
	Node* a = NULL;

	/* Let us create a unsorted linked lists to test the functions
	Created lists shall be a: 2->3->20->5->10->15 */
	Push(&a, 15);
	Push(&a, 10);
	Push(&a, 5);
	Push(&a, 20);
	Push(&a, 3);
	Push(&a, 2);

	/* Sort the above created Linked List */
	MergeSort(&a);

	printf("Sorted Linked List is: \n");
	printList(a);

	getchar();
}

/*
  Compute a new sorted list that represents the intersection
  of the two given sorted lists.（求两链表的交集）
  Note: The original lists should not be changed.
*/
Node* SortedIntersect(Node* a, Node* b) {
	Node* dummy = NewNode(0);
	Node* tail = dummy;
	while (a != NULL)
	{
		if (a->data == b->data)
		{
			Push(&tail->next, a->data);
			tail = tail->next;
			a = a->next;
			b = b->next;
		} else {
			a = a->next;
		}
	}
	return dummy->next;
}

void SortedIntersectTest() {
	/* Start with the empty lists */
	Node* a = NULL;
	Node* b = NULL;
	Node* intersect = NULL;

	/* Let us create the first sorted
	 linked list to test the functions
	 Created linked list will be
	 1->2->3->4->5->6 */
	Push(&a, 6);
	Push(&a, 5);
	Push(&a, 4);
	Push(&a, 3);
	Push(&a, 2);
	Push(&a, 1);

	/* Let us create the second sorted linked list
	Created linked list will be 2->4->6->8 */
	Push(&b, 8);
	Push(&b, 6);
	Push(&b, 4);
	Push(&b, 2);

	/* Find the intersection two linked lists */
	intersect = SortedIntersect(a, b);

	printf("\n Linked list containing common items of a & b \n ");
	printList(intersect);
	printList(a);
	printList(b);
	getchar();
}

void Reverse(Node** headRef) {
	Node* tail = NULL;
	for (Node *current = *headRef; current != NULL;) {
		MoveNode(&tail, &current);
	}
	*headRef = tail;
}

void ReverseTest() {
	struct node* head;
	head = BuildOneTwoThree();
	Reverse(&head); // head now points to the list {3, 2, 1}
	printList(head);
	getchar();
	DeleteList(&head); // clean up after ourselves
}

void RecursiveReverse(Node** headRef) {
	Node* first = *headRef;
	Node* rest = first->next;
	if (first == NULL || first->next == NULL) {
		return;
	}
	// printf("翻转前：");
	// printList(first);
	RecursiveReverse(&rest);

	first->next->next = first;
	first->next = NULL;

	*headRef = rest; //让headRef指针指向新的头
	// printf("翻转后：");
	// printList(*headRef);
}

void RecursiveReverseTest() {
	Node* head = NULL;

	Push(&head, 2);
	Push(&head, 4);
	Push(&head, 6);
	Push(&head, 8);

	printf("Given linked list\n");
	printList(head);
	RecursiveReverse(&head);
	printf("\nReversed Linked list \n");
	printList(head);
	getchar();
}

void Test() {
	Node *node = NULL, *ptr = NULL;
	Node *start = NULL, *Front = NULL, *Rear = NULL;
	char ch;
	do {
		ptr = node;
		node = NewNode(0);

		printf("Enter data:");
		scanf("%d", &node->data);

		if (start == NULL)
			start = node;
		else
			ptr->next = node;
		printList(start);
		printf("Do you want to continue(Y/N)? \n\n");
	} while (toupper((ch = getchar())) != 'N');
	getchar();
	printf("\nComplete Linked list: ");
	printList(start);

	// FrontBackSplit(start, &Front, &Rear);
	// RemoveDuplicates(start);
	AlternatingSplit(start, &Front, &Rear);
	printList(start);
	printf("\nFront: ");
	printList(Front);
	printf("\nRear: ");
	printList(Rear);
	getchar();
}

int main(int argc, char const *argv[])
{
	// SortedMergeTest();
	// MergeSortTest();
	// SortedIntersectTest();
	// ReverseTest();
	RecursiveReverseTest();
	return 0;
}
